package q456_find132pattern;

import java.util.Deque;
import java.util.LinkedList;

public class Solution_1 {
    public static void main(String[] args) {
        int[] nums = {-2, 1, 2, -2, 1, 2};
        Solution_1 s = new Solution_1();
        s.find132pattern(nums);
    }

    /*
    方法超时
     */
    public boolean find132pattern(int[] nums) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int[] firstBiggerNumIndex = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
                stack.pop();
            }
            firstBiggerNumIndex[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int Second;
        for (int i = 0; i < firstBiggerNumIndex.length; i++) {
            if (firstBiggerNumIndex[i] != -1) {
                Second = nums[firstBiggerNumIndex[i]];
                for (int j = firstBiggerNumIndex[i] + 1; j < nums.length; j++) {
                    Second = Math.max(Second, nums[j]);
                    if (nums[j] > nums[i] && nums[j] < Second) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
